﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" >
<head>  
    <title>CS155 Final Project - Alex Yin, Sayuri Soejima, and Simon Yang</title>
</head>
<body>

  <center>
  <H2> CS155 - Computer Graphics <br />
  Final Project: "Moving Gradients: A Path-Based Method for Plausible Image Interpolation"<br />
  Alex Yin, Sayuri Soejima, Simon Yang
</H2>


  <br />


The main paper referenced: <br />
  <a href="http://simonyang.info/interpolation.pdf">Interpolation Paper</a>

<br /><br />
  Other papers used/referenced in our implementation:

<br />

  <a href="http://www.cs.cornell.edu/rdz/papers/bvz-iccv99.pdf">
    Fast Approximate Energy Minimization via Graph Cuts
  </a>

 <br />

  <a href="http://www.cs.cornell.edu/~rdz/Papers/KZ-ICCV01-tr.pdf">
    Computing Visual Correspondence with Occlusions via Graph Cuts
  </a>
    
  </center>

<br /><br />

  <b>A wiki where we kept track of general progress/sources:</b><br />
  <a href="http://code.google.com/p/hmcinterpolation/wiki/Home">
    Google code wiki
  </a>

<br /><br />

  <b>Project Description</b><br />
  Given two input images, the goal of the project is to implement a system that allows
  us to come up with a plausible interpolation of the two images. There are two
  components to our project that we must consider. The first portion is the path algorithm.
  The algorithm finds a plausible path for each pixel, and uses that for interpolation.
  In order to accomplish the interpolation process, we use energy minimization techniques
  to calculate transition points.

  <br />
  <br />

<b> Algorithm Overview </b> <br />
We first create a gaussian pyramid for each of the input images. This allows us to find paths with arbitrary transition points without having an extremely large set of paths to consider. After generating the gaussian pyramids, we would start finding paths starting from the smallest layer of the pyramid. We pick paths for pixels based on a few metrics. A path defines two transition points between the two images for a pixel location. We constrain the two vectors that go towards the transition points to have the parallel, but opposite, directions. This is to ensure that movement of the transition points is uniform throughout the interpolation range. We want to minimize both correspondence (difference in the transition points in terms of gradient and color) and coherency (the difference in motion between the neighboring pixel paths). The paper proposes a graph cut method of minimizing the energy. Once we pick the correct path for a layer, we can move on to the next layer. <br /><br />

After completing in finding the path, we can then easily interpolate the new image by following the paths to find where the original pixel value should be. The paper proposes to use gradients instead of intensity for better results, especially in preserving edges.

<br /> <br />

  <b>Notes about our implementation</b><br />
  For interpolation values between 0.2 and 0.8, the quality of results may vary greatly depending on the run.
  
<br /><br />
  
  <b>How to run the program</b>
  <ul>
    <li>Compile the code and run the executable (the program is called "interpolation").</li>
    <li>Right click on the window and select "Process"->"Interpolate".</li>
    <li>There are 3 inputs: the first 2 inputs are .bmp files, and 
        the last input is a double between 0 and 1 (inclusive).</li>
    <li>Wait until the process finishes (may take several hours...).</li>
  </ul>
  
<br /><br />
  <b>Some of the problems we had during implementation</b>
  <ul>
    <li>
      We did try our best to follow the implementation described by the paper.  However, there were several areas within the implementation that we were unable to figure out.
    </li>
      <ul>
        <li>We spent a significant amount of time trying to understand the use of standard deviation in the correspondence function. We were stuck on the decision of whether or not to include the center pixel in the standard deviation calculation. We were also unable to look into the reference mentioned in the section because it was a book we didn't have access to. We also had some issues with edge cases when doing correspondence calculations.</li>
        <li>
          Another of the problems we encountered was dealing with the case when the transition points fall outside of the
          image boundaries. We currently essentially disallow any transition points outside the image. But this may be forcing some assumptions that would prevent the path finding algorithm from finding the optimal path. We also did not have time to investigate occlusion handling.
        </li>
    </li>
    </ul>
    <li>Graph cuts.  The paper provided a good overview of the overall interpolation process, but only briefly referenced two graph-cuts papers for the energy minimization implementation. Although the referenced papers described in detail in graph-cuts algorithm, it was unclear from the main paper how to apply the graph-cuts to our particular energy minimization problem.  Therefore, under Professor Z's recommendation, we implemented a hill-climbing approach for energy minimization instead.</li>
    <li>We tried tracking down and emailing the authors of the paper, but did not receive any responses.</li>
    <li>The algorithms took a long time to run, which made it hard to test and verify results.</li>
    <ul>
      <li>For a 256x256 greyscale image 
          (the image of the girl, taken from the paper example), it took over an hour to run.</li>
      <li>Path validation function is constraining the initial random assignment of paths.</li>
    </ul>
    
  </ul>

<br /><br />

  <b>Suggested grading rubric/our work:</b> (58/75 total points) <br />
  <ul>
    <li>23/40 points: Path implementation</li>
    <ul>
      <li>5/5 points: Brief write-up from each member about the path 
          implementation in the paper, to demonstrate our understanding. 
          As part of this process, we will each read everyone’s write-up, 
          in order to catch any misunderstandings before getting into heavy implementation.</li>
      <ul>
        <li>Write-ups were written by all 3 of us.  It is posted on the Google code wiki.</li>
      </ul>
      <li>8/10 points: Path construction – determining possible paths from the input images.</li>
      <ul>
        <li>This portion of the code is at least mostly working--it IS generating paths, and 
             we are able to work with them.  However, there is something going awry with the 
             actual paths, so it is not completely worthy of 10 points.</li>
      </ul>
      <li>8/10 points: Computing transition points. This will involve energy-minimization, or min-cost.</li>
      <ul>
        <li>We are correctly computing transition points for arbitrary paths.  
        However, we are not certain if the paths we are getting from this process are 
        actually the best ones available.  However, we believe we should get most of the points 
        for this rubric item, because the calculation should be correct (although it is 
        hard to test for path-correctness with an arbirary image).</li>
      </ul>
      <li>0/10 points: Occlusion handling.</li>
      <ul>
        <li>We were not able to get to Occlusion handling within the timeframe of this project.</li>
      </ul>
      <li>2/5 points: Use gradients instead of image intensities during interpolation, 
          to improve the interpolation results (particularly with edges).</li>
      <ul>
        <li>We were not able to get to using gradients during interpolation, but we did 
        write a gradients function, which we used in energy minimization.</li>
      </ul>
    </ul>   
    <li>25/25 points: Energy function</li>
    <ul>
      <li>
        5/5 points: Brief write-up from each member about the energy function
        implemented in the paper, to demonstrate our understanding.
        As part of this process, we will each read everyone’s write-up,
        in order to catch any misunderstandings and to further our understanding.
      </li>
      <ul>
        <li>Write-ups were written by all 3 of us.  It is posted on the Google code wiki.</li>
      </ul>
      <li>10/10 points: Graph cuts.</li>
      <ul>
        <li>As recommended by Prof. Z during a meeting (on 11/30), we decided not to 
        go with the graph cuts method, but to instead go with a hill-climbling method.  
        Unfortunately, this may be the reason that our algorithm takes a ridiculously 
        long time to run (past an hour and a half), although we are not completely certain.  
        However, we DID completely implement the other hill-climbing method, 
        which would be the equivalent of having completed   the whole graph cuts implementation.
        </li>
      </ul>
      <li>10/10 points: Computing a local minimum.</li>
      <ul>
        <li>We do compute the local minimum, as specified.</li>
      </ul>
    </ul>
    <li>10/10 points: HTML write-up describing the features we implemented</li>
  </ul>

  <br />
  
  <b>Checklist for other work:</b> (25 total points) <br />
  <ul>
    <li>10 points: Proposal - 2-3 page proposal submitted, and it is also on our wiki (linked above).
        Everything required should be included in the proposal, which we also emailed to Prof. Z.</li>
    <li>5 points: Wiki - We kept a wiki, and each kept an individual log of the work done and 
        progress made throughout the project.  Individual logs may be in different places, according 
        to each person's preference (either on our Google code wiki, or on our individual CS Twikis).</li>
    <li>5 points: Concept presentation - Given in class.</li>
    <li>5 points: Final presentation - To be given on Thursday, 12/10/2009.</li>
  </ul>


</body>
</html>
